๋ฌธ์
Programmers - ์ํ์ฅ ๋๋๊ธฐ
๐ Logic
private int dfs(int cur, int limit) {
// ์ผ์ชฝ๊ณผ ์ค๋ฅธ์ชฝ ์์ ํธ๋ฆฌ์์ ๋์ด์ค๋ ์ธ์ ์
int leftValue = 0, rightValue = 0;
if (left[cur] != -1) leftValue = dfs(left[cur], limit);
if (right[cur] != -1) rightValue = dfs(right[cur], limit);
// ๋ ์์ ํธ๋ฆฌ์์ ๋์ด์ค๋ ์ธ์์ ๋ชจ๋ ๊ฐ๋นํ ์ ์๋ ๊ฒฝ์ฐ, ๊ทธ๋ฃน ์๋ ์ฆ๊ฐํ์ง ์์
if (x[cur] + leftValue + rightValue <= limit)
return x[cur] + leftValue + rightValue;
// ๋ ์์ ํธ๋ฆฌ ์ค ์์ ๊ฐ์ ํฉ์ณ์ผ ๊ฐ๋นํ ์ ์๋ ๊ฒฝ์ฐ, ์ฆ ์์ ๋
ธ๋ ํ๋๋ฅผ ๋๋ ๊ฒฝ์ฐ๋ก ๊ทธ๋ฃน์ด 1๊ฐ ์ถ๊ฐ
if (x[cur] + Math.min(leftValue, rightValue) <= limit) {
count++;
return x[cur] + Math.min(leftValue, rightValue);
}
// ๋ ์์ ํธ๋ฆฌ ๋ชจ๋ ๊ฐ๋นํ ์ ์์ด์ ๋ ๋ค ๋๋ ๊ฒฝ์ฐ, ๊ทธ๋ฃน์ด 2๊ฐ ์ถ๊ฐ
count += 2;
return x[cur];
}
- ์ฃผ์ด์ง ํธ๋ฆฌ์์ ๊ฐ ๊ทธ๋ฃน์ ์๋ฅผ x๋ช ์ผ๋ก ์ ํํ ๋ ํ์ํ ๊ทธ๋ฃน์ ์๋ฅผ ๊ณ์ฐํด์ผ ํ๋ค.
-
๊ฐ ๊ทธ๋ฃน์ ์๋ฅผ x๋ช ์ผ๋ก ์ ํํ ๋ ํ์ํ ๊ทธ๋ฃน์ ์๋ฅผ ๊ณ์ฐํ๊ธฐ ์ํด ๊ทธ๋ฆฌ๋๋ฅผ ์ฌ์ฉํ์ฌ ์ต๋ํ ๊ทธ๋ฃน ์์ฑ์ ๋ฏธ๋ฃจ๋ฉด์ ์๋ก ์ฌ๋ ค๋ณด๋ธ๋ค.
- ๋ถ๋ชจ ๋ ธ๋์์ ์์ ๋ ธ๋๋ฅผ ๋ ์ด์ ๊ฐ๋นํ ์ ์๋ ๊ฒฝ์ฐ, ๊ฐ์ด ๋ ์์ ๋ ธ๋๋ฅผ ์ฑ๊ธฐ๊ณ ๋ค๋ฅธ ๋ ธ๋๋ฅผ ์๋ผ๋ธ๋ค.
-
๊ทธ๋ฃน์ผ๋ก ๋๋ ๋ ์๋ 3๊ฐ์ง ๊ฒฝ์ฐ๊ฐ ์กด์ฌํ๋ค.
- ๋ถ๋ชจ ๋ ธ๋๊ฐ ์์ ๋ ธ๋ ๋ชจ๋ ์ฑ๊ธฐ๊ธฐ : ๊ทธ๋ฃน + 0, ์ธ ๋ ธ๋์ ํฉ์ ๋ ๋ถ๋ชจ ๋ ธ๋๋ก ์ ๋ฌ
- ์์ ๋ ธ๋ ์ค 1๊ฐ์ ๋ถ๋ชจ ๋ ธ๋๋ฅผ ์ฑ๊ธฐ๊ธฐ : ๊ทธ๋ฃน + 1, ์์ ๋ ธ๋ ์ค ์ต์๊ฐ + ๋ถ๋ชจ ๋ ธ๋์ ๊ฐ์ ๋ ๋ถ๋ชจ ๋ ธ๋๋ก ์ ๋ฌ
- ์์ ๋ ธ๋๋ฅผ ํ๋๋ ์ฑ๊ธฐ์ง ์๊ธฐ : ๊ทธ๋ฃน + 2, ๋ถ๋ชจ ๋ ธ๋์ ๊ฐ๋ง ๋ ๋ถ๋ชจ ๋ ธ๋๋ก ์ ๋ฌ
- DFS๋ฅผ ํตํด ๋ฆฌํ ๋ ธ๋๋ถํฐ ๊ฐ์ ์๋ก ์ฌ๋ ค๋ณด๋ด๋ ์์ ์ ๋ฐ๋ณตํ๋ค.
๐ CODE
์ฝ๋ ๋ณด๊ธฐ/์ ๊ธฐ๐ซ
import java.util.*;
class ExamRoom {
int n;
int root;
int count = 0;
int[] left;
int[] right;
int[] x; // ์ํ์ฅ์ ์์ ์ธ์
int[] parent;
public ExamRoom(int[] num, int[][] links) {
this.n = num.length;
parent = new int[n];
left = new int[n];
right = new int[n];
x = new int[n];
Arrays.fill(parent, -1);
init(num, links);
setRoot();
}
private void init(int[] num, int[][] links) {
for (int i = 0; i < n; i++) {
int l1 = links[i][0];
int l2 = links[i][1];
// ์์ ์ง์
left[i] = l1;
right[i] = l2;
x[i] = num[i];
// ๋ถ๋ชจ ์ง์
if (l1 != -1) parent[left[i]] = i;
if (l2 != -1) parent[right[i]] = i;
}
}
// parent[i]๊ฐ -1์ด๋ผ๋ฉด root
private void setRoot() {
for (int i = 0; i < n; i++) {
if (parent[i] == -1) {
root = i;
return;
}
}
}
public int getAnswer(int k) {
// start๋ num์ ์ต๋๊ฐ
int start = x[0];
for (int i : x)
start = Math.max(start, i);
// end๋ num์ ์ต๋๊ฐ * num์ ๊ธธ์ด
int end = start * n;
while(start < end) {
int mid = (start + end) / 2;
if (solve(mid) <= k) end = mid;
else start = mid + 1;
}
return start;
}
private int solve(int limit) {
count = 0;
dfs(root, limit);
// ๋งจ ๋ง์ง๋ง์ ๋จ์ ์ธ์๋ค์ ๋ํ ๊ทธ๋ฃน ํ๋ ์ถ๊ฐ
return count + 1;
}
private int dfs(int cur, int limit) {
// ์ผ์ชฝ๊ณผ ์ค๋ฅธ์ชฝ ์์ ํธ๋ฆฌ์์ ๋์ด์ค๋ ์ธ์ ์
int leftValue = 0, rightValue = 0;
if (left[cur] != -1) leftValue = dfs(left[cur], limit);
if (right[cur] != -1) rightValue = dfs(right[cur], limit);
// ๋ ์์ ํธ๋ฆฌ์์ ๋์ด์ค๋ ์ธ์์ ๋ชจ๋ ๊ฐ๋นํ ์ ์๋ ๊ฒฝ์ฐ, ๊ทธ๋ฃน ์๋ ์ฆ๊ฐํ์ง ์์
if (x[cur] + leftValue + rightValue <= limit)
return x[cur] + leftValue + rightValue;
// ๋ ์์ ํธ๋ฆฌ ์ค ์์ ๊ฐ์ ํฉ์ณ์ผ ๊ฐ๋นํ ์ ์๋ ๊ฒฝ์ฐ, ์ฆ ์์ ๋
ธ๋ ํ๋๋ฅผ ๋๋ ๊ฒฝ์ฐ๋ก ๊ทธ๋ฃน์ด 1๊ฐ ์ถ๊ฐ
if (x[cur] + Math.min(leftValue, rightValue) <= limit) {
count++;
return x[cur] + Math.min(leftValue, rightValue);
}
// ๋ ์์ ํธ๋ฆฌ ๋ชจ๋ ๊ฐ๋นํ ์ ์์ด์ ๋ ๋ค ๋๋ ๊ฒฝ์ฐ, ๊ทธ๋ฃน์ด 2๊ฐ ์ถ๊ฐ
count += 2;
return x[cur];
}
}
class Solution {
public int solution(int k, int[] num, int[][] links) {
ExamRoom er = new ExamRoom(num, links);
return er.getAnswer(k);
}
}
โ๏ธ Review
- ์ฒ์ ๋ณด๋ ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํ๋ ๋ฌธ์ ์ฌ์ ์ฐธ๊ณ ๋ฅผ ์ฐฌ์ฐฌํ ์ฝ์ด๋ณด๋ฉด์ ์ดํดํ๋ ค๊ณ ํ๋ค.
- ๊ฐ ๊ทธ๋ฃน์ ์๋ฅผ x๋ช ์ผ๋ก ์ ํํ ๋ ๊ทธ๋ฃน์ ์๊ฐ k๊ฐ ์ดํ์ธ์ง๋ฅผ ํ๋จํ๋ ๊ฒฐ์ ๋ฌธ์ ์ฆ, Parametric Search๋ฅผ ์ฌ์ฉํ๋ ๋ฌธ์ ๋ฅผ ์ฒ์ ์ ํ ๊ฒ ๊ฐ๋ค... ๋ฌธ์ ๋ฅผ ๋ค์ํ๊ฒ ํ์ด๋ณผ ์ ์์ด์ผ ๊ฒ ๋ค.
๐ ์ฐธ๊ณ
[ํ๋ก๊ทธ๋๋จธ์ค] ์ํ์ฅ ๋๋๊ธฐ / 2021 ์นด์นด์ค ์ฑ์ฉ์ฐ๊ณํ ์ธํด์ญ - JAVA